/*
	file name:node3.c
	file object:实现对链表的增删改查
	created time: 2022-03-23
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<errno.h>
#include<pthread.h>
#include<malloc.h>
#include<stdbool.h>


#define MAX_SIZE 100
void sys_err(char* str){
	perror(str);
	exit(1);
}

typedef struct Node{
	int data;
	struct Node* pNext;
}NODE,*PNODE;

PNODE create_list(void);	//创建链表
int length_list(PNODE pHead);	//获取链表长度
void traverse_list(PNODE pHead);	//遍历链表
bool is_empty(PNODE pHead);	//判断链表是否为空
bool delete_list(PNODE pHead,int pos,int* del_val);	//删除链表某个元素
bool insert_list(PNODE pHead,int pos,int insert_val);	//插入某个元素
bool modified_list(PNODE pHead,int pos,int mod_val);	//更改某个元素的值
int search_list(PNODE pHead,int target,int* nums);	//搜索某个值,成功：返回1,并且将值存入nums；异常失败：返回-1；未搜索到搭配的元素，返回0
void sort_list(PNODE pHead);	//链表排序

int main(int argc,char* argv[]){
	int nums[MAX_SIZE]={0},i=0;
	int* del_val=(int*)malloc(sizeof(int));
	PNODE pHead=NULL;	//初始化一个头指针
	pHead=create_list();	//创建一个链表
	printf("the length of the list is %d \n",length_list(pHead));
	traverse_list(pHead);

	if(delete_list(pHead,3,del_val)){
		printf("The deleted number is %d\n",*del_val);
	}else{
		printf("Error! Failed to delete the number!\n");
	}
	printf("Deleted list is followings:\n");
	traverse_list(pHead);

	if(insert_list(pHead,6,1000)){
		printf("Insert success!\n");
	}else{
		printf("Error! Failed to insert!\n");
	}
	printf("Inserted list is followings:\n");
	traverse_list(pHead);

	if(modified_list(pHead,2,1314)){
		printf("modify success!\n");
	}else{
		printf("Error! Failed to modify!\n");
	}
	printf("Modified list is followings:\n");
	traverse_list(pHead);


	int temp_val=search_list(pHead,521,nums);
	if(temp_val == 1){
		printf("The matched node is followings:\n");
		for(i=0;nums[i]!=0;i++){
			printf("%d ",nums[i]);
		}
	}else if(temp_val == 0){
		printf("No matched node!\n");
	}else if(temp_val == -1){
		printf("Error! Failed to match!\n");
	}
	
	sort_list(pHead);
	printf("The sorted list is followings:\n");
	traverse_list(pHead);

	return 0;
}

PNODE create_list(void){
	int i=0,length=0;
	int value=0;
	PNODE pHead=(PNODE)malloc(sizeof(PNODE));
	if(pHead == NULL){
		printf("failed to distribute memory!\n");
		printf("The program has exit!\n");
		exit(-1);
	}
	PNODE pTail=pHead;
	pTail->pNext=NULL;
	printf("Please input your wanted length of the list: ");
	scanf("%d",&length);
	
	for(i=0;i<length;i++){
		printf("Please input the value of the %dth node of the list: ",i+1);
		scanf("%d",&value);
		PNODE pNew=(PNODE)malloc(sizeof(PNODE));
		if(pNew == NULL){
			printf("failed to distribute memory!\n");
			printf("the program has been exit!\n");
			exit(-1);
		}
		pNew->data=value;
		pTail->pNext=pNew;
		pNew->pNext=NULL;
		pTail=pNew;
	}
	return pHead;
}

int length_list(PNODE pHead){
	PNODE p=pHead->pNext;
	int length=0;
	while(p !=NULL){
		length++;
		p=p->pNext;
	}
	return length;
}

void traverse_list(PNODE pHead){
	PNODE p=pHead->pNext;
	while(p !=NULL){
		printf("%d ",p->data);
		p=p->pNext;
	}
	printf("\n");
	return;
}

bool is_empty(PNODE pHead){
	if(pHead->pNext ==NULL)
		return true;
	else 
		return false;
}
void sort_list(PNODE pHead){
	int i,j,t;
	int length=length_list(pHead);
	PNODE p,q;
	for(i=0,p=pHead->pNext;i<length-1;i++,p=p->pNext){
		for(j=i+1,q=p->pNext;j<length;j++,q=q->pNext){
			if(p->data > q->data){
				t=p->data;
				p->data=q->data;
				q->data=t;
			}
		}
	}
	
	return;
}

bool insert_list(PNODE pHead,int pos,int insert_val){
	int i=0;
	PNODE p=pHead;
	while(p != NULL && i<pos-1){
		p=p->pNext;
		i++;
	}

	if(i>pos-1 || p == NULL)
		return false;
	PNODE pNew=(PNODE)malloc(sizeof(PNODE));
	if(pNew == NULL){
		printf("failed to distribute memory!\n");
		printf("Program has exit!\n");
		exit(-1);
	}
	pNew->data=insert_val;
	pNew->pNext=p->pNext;
	p->pNext=pNew;
	return true;
}

bool delete_list(PNODE pHead,int pos,int* del_val){
	int i=0;
	PNODE p=pHead;
	while(p->pNext != NULL && i<pos-1){
		p=p->pNext;
		i++;
	}

	if(i>pos-1 || p->pNext == NULL)
		return false;
	PNODE q=p->pNext;
	*del_val =q->data;

	p->pNext=p->pNext->pNext;
	free(q);
	q=NULL;

	return true;
}

bool modified_list(PNODE pHead,int pos,int mod_val){
	int i=0;
	PNODE p=pHead;
	while(p->pNext !=NULL && i<pos-1){
		p=p->pNext;
		i++;
	}

	if(i>pos-1 || p->pNext == NULL)
		return false;

	p->pNext->data=mod_val;
	p=NULL;

	return true;
}

int search_list(PNODE pHead,int target,int* nums){
	int i=0,j=0;
	int length=length_list(pHead);
	PNODE p=pHead;
	while(p->pNext !=NULL && i<length-1){
		p=p->pNext;
		i++;
		if(p->data == target){
			nums[j]=i;
			j++;
		}	
	}

	if(i>length-1 || p->pNext == NULL)
		return -1;

	if(p->pNext->data == target){
		nums[j]=length;
		return 1;
	}else if(j == 0){
		return 0;
	}
	return 0;
}
